1. Field of the Invention
This invention relates to a method and apparatus for decoding convolutionally encoded signals. Such signals are commonly used in communications and recording systems which employ error correction to combat signal corruption. The convolutional decoders discussed here are based on the Viterbi algorithm, in which weights are calculated for transitions which form survivor paths through a decoder trellis. The decoding then takes the form of tracing the most likely survivor path. More specifically, this invention concerns a novel method for storing survivor paths which when implemented leads to a significant reduction in circuit complexity and silicon area needed to implement the convolutional decoder apparatus hereof.
2. Description of the Relevant Art
Error correction codes function by accepting input data symbols and processing them in such a way as to add some redundancy to the symbol sequence. One way this is commonly done is to increase the number of symbols in the sequence, so that for every k symbols that enter the encoder, n symbols are dispatched by the encoder. The input and output symbols are generally binary digits (bits), and the information throughput is represented as a code rate of k/n.
The most popular form of error correction codes are block codes. Block codes are characterized by the feature of state-independent decodability. A block encoder can be implemented as a lookup table in which the input data word is used as an address, and the code word corresponding to the input data word is given by the contents of the table at that address. In this way a one-to-one mapping from input data words to code words is achieved. A simple decoding algorithm is to compare the received code word to all possible code words, choose the "closest" code word, and use the chosen code word as an address in a second lookup table that contains the input data word which corresponds to the chosen code word. The state-independence is a result of the one-to-one mapping that ensures each code word has only one possible interpretation. One drawback of block coding is that for adequate performance, many systems require codes with very long block lengths, necessitating large memories or more complex encoding and decoding algorithms.
As an alternate approach, short block lengths can be used, but some restrictions are added to which code words can be used. With block coding, each of the code words could be used at any time as dictated by the current input data word. This is not the case with convolutional coding, where the code words which can be used are influenced by previous input data words as well as the current input data word. This increases the effective "length" of code words by extending the range of influence of an input data word beyond one code word. As a consequence, however, there is not a one-to-one mapping from the input data words to code words, and the encoding and decoding processes are more involved.
FIG. 1 illustrates one example of a convolutional encoder. Encoder 110 includes a series of adders 116 interposed between a shift registers 114 and a time multiplexer 118. Encoder 110 accepts one bit at each time step and produces three bits. Shift register 114 shifts its contents to the right one bit per time interval, accepting a new bit from the input data stream 112 in the process. Shift register 114 exemplifies a four-bit wide register which contains the current input data bit and the three previous data bits. The three previous bits are considered to form the "encoder state". When the shift register shifts again to the right, the current input data bit will become the most significant bit of the encoder state, thereby causing a transition to the new state. As more input data enters the shift register and the register again shifts, another transition occurs. As these transitions continue to occur, a sequence forms. This sequence of transitions between encoder states is often referred to as a path.
Associated with each transition in the path is a three bit code word that is formed based on the current input bit and the current encoder state. The contents of the shift register 114 are added together in different ways by three adders 116. The topmost adder adds the values of the first, third and fourth bits in the shift register. The middle adder adds the values of the first, second and fourth bits, and the bottom adder adds the values of all four bits. In each case, the summation is done modulo two, so that the output of the adder is one if the result is odd, and zero if the result is even. The adder outputs are passed to the time multiplexer 118 to form the output code word. Time multiplexer 118 then switches three times to pass its contents to the output line 120 before the next input bit is accepted. The rate of this encoder is thus 1/3. The number of encoder states is 2.sup.3 =8 since three previous input bits are held in shift register 114.
In summary, convolutional encoder 110 accepts one input bit (I.sub.1) per time step and calculates a three bit code word based on the input bit and the encoder state, wherein the encoder state shown comprises the past three input bits (B.sub.1, B.sub.2 and B.sub.3). The sequence of code words passes through a transmission channel which is typically subject to interference (i.e. channel disturbances which may include random noise) that may corrupt the sequence of code words. To decode the code word sequence, a decoder will attempt to reverse the encode process and decide what the input bit is, based on the code word and state of the encoder. However, the decoder does not know for certain what the state of the encoder is, so the decoder often maintains a decision unit for each possible encoder state. The decoding decision will be based on the most likely sequence of encoder states as determined by the sequence of code words.
To decode the code word sequence, a time-expanded version of the encoder state transition diagram is formed. When all of the possible transitions from a state at time t to a state at time t+1 are shown, the resulting diagram is one stage (hereafter called a time step) of a trellis. FIG. 2 depicts an example of one time step of a decoder trellis. The eight states the encoder could be in at a given time t are listed on the left in FIG. 2, and the eight states the encoder could be in at time t+1 are listed on the right. The lines (hereafter referred to as edges) in FIG. 2 represent the possible state transitions. For example, if at time t the encoder is in state 000 and the current input bit is 1, at time t+1 the encoder will be in state 100. This follows from the adder configuration shown in the example encoder of FIG. 1. Namely, if B.sub.1, through B.sub.3 at time t are all 0 and input bit I.sub.1, is 1, then the code word C.sub.1 through C.sub.3 output from adders 116 is 111, respectively. That code word represents an ideal transition from state 000 at time t to 100 at time t+1, given an input bit I.sub.1, of 1. The only other possible transition from state 000 at time t occurs when the current input bit is 0, which results in a transition to state 000 at time t+1. For all states shown, the uppermost edge illustrates a state transition resulting from a current input bit of 0, and the lower edge illustrates a state transition resulting from a current input bit of 1. The trellis shown in FIG. 2 thereby duplicates the effects of shift register 114 which produces a state transition by shifting the current input bit into the most significant bit position of the encoder state.
Shown in FIG. 2 are the code words that correspond to each transition from state t to t+1. The code words are those produced by encoder 110 based on the current input bit and the encoder state. For an input bit of 0, the encoder state can transition from, e.g., 010 at time t to 001 at time t+1 having an output code word of 101. This correspondence was determined from FIG. 1 where it can be seen that when I.sub.1, B.sub.1, B.sub.2, and B.sub.3 are 0, 0, 1, and 0, respectively, adders 116 produce a 101 into bit locations C.sub.1, C.sub.2 and C.sub.3 of register 118. Similarly, the encoder state transition from 010 at time t to 001 at time t+1 having an output code word of 101.
FIG. 2b shows a time expansion, i.e., multiple time steps beyond simply t and t+1 of FIG. 2). The time steps indicate a decoder trellis beginning at time t=0 to time t=6. At each time step, the decision units of the decoder contain the weight of the most likely path to the state of interest. Thus, the decoder trellis contains multiple paths from an initial state to a given state several time steps later; however, only one path has the lowest weight and therefore is the most likely path. The most likely path to a particular state within a given time step is found by starting at that particular state at that given time step and tracing backward along the chosen transitions which are drawn with the thick lines. If no more code words are received, the decoding may be performed by choosing the state at time t=6 with the smallest weight as the most likely encoder state and following the most likely path to that state from left to right. An input bit of 0 is decoded if the path follows the top transition from a state, and a 1 is decoded if the path follows the bottom transition from a state. In FIG. 2b the decoded data as indicated by the trail of thickest lines found by tracing backward from state 000 at time t=6 is 010000. The trail of thickest lines is herein referred to as the path having the lowest weight, e.g., "4" at time t=6 in the example provided. Details on the calculation of the weights and selection of the transitions follow.
The decoder is initialized by setting the weight of the first state (e.g. state A) at time t=0 to zero and the rest of the weights of states at time t=0 to a large number (in the figure this number is represented by X). This is done because it has been decided ahead of time that the initial state of the encoder is 000. Thereafter as code words come in at each time step, a metric (defined here to be a measure of difference between two signals) is formed for each code word which effectively measures the distance from the signal received at that time step to the code word. Classically, the metric used is the squared Euclidean distance. As an example, assume that at time t=0 the received signal is 100. Then the metrics M for each of the eight possible code words are (c.sub.1 -1).sup.2 +(c.sub.2 -0).sup.2 +(c.sub.3 0).sup.2 which yields the following results: ##EQU1## where M.sup.t.sub.c equals the metric at time t for code word c.
Each state at time t&gt;0 has associated with it a weight and a path. As will be explained in greater detail further below, the weight associated with each state is defined as the sum of the metrics formed by the most likely path to that state. In the example provided in FIG. 2b, the weights of each state at state t=1 starting at the top state and traversing downward are 1XXX2XXX. Likewise the weights of each state at state t=6 starting at the top state are 45765666. The path is the most likely sequence of transitions that would have been taken by the encoder if indeed it is in that state. As an example, the received code word upon the decoder is 100, followed by 010, followed by 111, etc. However, instead of 100 at time t=0, the decoder should have received 000 or 111. The distance (metric) between the received signal and code word 000 is 1. Thus, the transition from state A in state t=0 to state B at time t=1 has a metric of 1. The weight of a transition is found by adding the metric to the weight of the state from which it originates. The transition from state A to state B thus has a weight of 0+1. Conversely, the distance between 100 and 111 (i.e., code word for input bit of 1 and a transition from state 000 to state 100--shown in FIG. 2) is 2. Thus, the metric from state A to state C is 2. The weight of the transition from A to C is then 0+2. The weight of state B or state C is the minimum weight of the incoming transitions. Thus, since the weight of the transition from state A to state B is 1, and the weight of the other incoming transition is a large number, then the weight of state B is 1. Similarly, the weight of state C is 2. The transitions which are chosen as having the minimum weights become path extensions. If at state C, the transition from state A to state C is chosen as the incoming transition with minimum weight, the most likely path to state C becomes the most likely path to state A plus the transition from state A to state C.
At any given time the encoder has only one state, but the decoder maintains a decision unit for all possible encoder states. Hence, each node in the decoder trellis corresponds to a decision unit. The decision units each track the weight of one state, and their decisions are passed to a memory unit which tracks the corresponding paths.
The weight associated with each state is defined as the sum of the metrics formed by the most likely path to that state. In the decoder trellis shown in FIG. 2b, each of the paths to the states at time t will have two possible extensions formed by the two transitions from each possible encoder state. The weight of each state at time t+1 is found by choosing the minimum weight of the two incoming transitions, where the weight of a transition is defined as the sum of the weight of the state it originates from and the metric of the code word that corresponds to that transition. The new path for the state at time t+1 is then the path to the originating state (at time t) that was chosen plus the transition.
The aforesaid decoding method was conceived by A. J. Viterbi who realized that any paths which merged to a common encoder state would have the same possible extensions and hence would not possess any distinguishing characteristics beyond that point. Therefore, making a decision at the merge point does not cause any loss of optimality, but will significantly reduce the decoding complexity since only a constant number of paths needed to be kept in memory. Even so, the decoding algorithm outlined above still possesses significant complexity in that each edge of the decoder trellis requires the calculation of a weight value, and a comparison and selection process must be performed to determine the transition with the minimum weight.
As an exercise to illustrate the complexity of the decoder, consider the steps taken by the decoder to update the state weights after a code word is received. First, a metric is calculated for each of the possible code words. For this example that translates into three additions, three squarings, and two more additions for each of eight code words yields 40 additions and 24 multiplications. Second, a weight is calculated for each edge in the trellis diagram. For this simple example there are 16 edges, necessitating 16 additions. Third, for each state all the weights of the incoming transitions must be compared to determine the smallest. The two edges per state in this example need only 1 comparison, yielding a total of 8. In total, 56 additions, 24 multiplications, and 8 comparisons are needed per time step. One technique for reducing the number of operations which perform the metric calculation described in the first step will be outlined hereinafter. One of the major concerns which remains to developers is the number of operations needed for the second and third steps. The number of edges in convolutional codes is an exponential function.
In the example provided, each state has two incoming edges, so only one comparison and selection is necessary to determine the transition with the minimum weight. In the general case, the number of edges entering a state is 2.sup.r (r is an integer determined by the decoder trellis), which requires r rounds of comparison and selection. In each round of the compare and select process, the edges are grouped into pairs and compared. Of the two, the edge representing the transition with the smaller weight is "selected", which means only that the other edge is dropped from candidacy since it can no longer represent the minimum weight transition. Consequently in each round, half of the edges are dropped from candidacy, and after r rounds, only the edge representing the minimum weight transition remains. The minimum weight transition for a state is referred to as a "survivor", the weight associated with the survivor is referred to as the survivor weight, and the path associated with the survivor is referred to as the survivor path. In the example depicted in FIG. 2b, the survivor path is illustrated with a sequence of thicker lines extending from states ABDEFGH. The survivor weight is the weight of the survivor path culminating at state H as having a weight of 4. State H weight is the sum of all previous transition weights within the survivor path as determined by the summation of the immediate preceding state weights and the metric between the preceding state and the state of interest.
Comparison and selection process must be performed for all states and for every code word received. Computational overhead for a Viterbi decoder can therefore be substantial. As shown in FIG. 3, Viterbi decoder 130 may be divided into two sub-units: an add-compare-select array (ACS array) 134 and a survivor path unit (SPU) 136. The metric calculation, addition, weight comparison and survivor path selection all take place within the ACS array. Thus, ACS array 134 contains the weight values at each state, as a progression along survivor path. The weight values are necessary, when making a comparison to other weights in other paths, to determine a survivor path. The compilation and comparison functions which take place within the ACS array 134 allow determination of path extensions. Signals indicating the extensions to the survivor paths are passed from the ACS array to the SPU which then updates the survivor paths. The SPU also functions to provide decoded symbol decisions based on the survivor paths. Two popular methods exist for implementing the SPU: the register exchange method, and the traceback method. Only the traceback method is discussed herein.
To illustrate the traceback method, a random access memory (RAM) is used. The RAM is organized into rows and columns. The columns represent time steps, i.e., t=0, t=1, etc. in the decoder trellis, and the rows represent the states, i.e., B,C, etc. at each time step. Each location in the RAM is assumed to hold a pointer to a state in the previous column, the state from which the surviving path to the current state originates. Note that this pointer may take the form of the input bit I.sub.1, which would have caused the chosen transition to the current state. This approach requires the addition of some external logic gates which generate the address of the state in the previous column when given the address of the current state and the contents of the current state.
The traceback method operates in the following manner: At each time step, the chosen transitions are stored in a column. One state is chosen as a starting point, and a traceback begins. The traceback consists of repeated reads from the RAM, each read accessing a column which precedes the column last accessed. The row used in each read is specified by the contents of the location last read. In this manner, it is possible to "trace backward" through the RAM and, more specifically, through the decoder trellis as described in FIG. 2b. After tracing backward a fixed number of steps, the last transition is rendered as a decoded bit in similar fashion to the previous method.
Note that in the traceback method, many reads must be performed during each decoding cycle. This places very demanding requirements on the speed of the RAM. Several approaches have been taken in an attempt to address this problem. Utilizing the principle that speed of a RAM typically inversely proportional to its size, some of these approaches focus on substituting several smaller RAM arrays for one larger RAM. Whatever speed is gained in the RAM operation, design complexity is increased by requiring additional decode, read/write, and pointer logic, and the associated requirement for a larger silicon chip area.